package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/12/11 13:21
 * @description：https://leetcode-cn.com/problems/online-election/
 */
public class 在线选举 {
    @Test
    public void test() {
        TopVotedCandidate topVotedCandidate =
                new TopVotedCandidate(new int[]{0, 1, 1, 0, 0, 1, 0}, new int[]{0, 5, 10, 15, 20, 25, 30});
        System.out.println(topVotedCandidate.q(3));
        System.out.println(topVotedCandidate.q(12));
        System.out.println(topVotedCandidate.q(25));
        System.out.println(topVotedCandidate.q(15));
        System.out.println(topVotedCandidate.q(24));
        System.out.println(topVotedCandidate.q(8));
    }

    /*
    class TopVotedCandidate {
        private final List<Integer> list = new ArrayList<>();
        private final Map<Integer, Integer> map = new HashMap<>();

        public TopVotedCandidate(int[] persons, int[] times) {
            int[] person_tickets = new int[5000];
            int max_tickets = 0;
            int max_tickets_person_no = -1;
            int n = times.length;
            for (int i = 0; i < n; i++) {
                int person_ticket = ++person_tickets[persons[i]];
                if (person_ticket >= max_tickets) {
                    int time = times[i];
                    max_tickets = person_ticket;
                    if (max_tickets_person_no != persons[i]) {
                        max_tickets_person_no = persons[i];
                        list.add(time);
                        map.put(time, max_tickets_person_no);
                    }
                }
            }
        }

        public int q(int t) {
            return map.getOrDefault(binary_search(t), null);
        }

        private int binary_search(int t) {
            int l = 0;
            int r = list.size() - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (list.get(mid) <= t) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            return list.get(l);
        }
    }
     */


    class TopVotedCandidate {
        private int[] times;
        // 存储每个时刻投票后的领先的候选人编号
        private final Map<Integer, Integer> map = new HashMap<>();
        public TopVotedCandidate(int[] persons, int[] times) {
            this.times = times;
            int[] person_tickets = new int[5000];
            int max_tickets = 0;
            int max_tickets_person_no = 0;
            int n = times.length;
            for (int i = 0; i < n; i++) {
                int person_ticket = ++person_tickets[persons[i]];
                if (person_ticket >= max_tickets) {
                    max_tickets = person_ticket;
                    max_tickets_person_no = persons[i];
                }
                map.put(times[i], max_tickets_person_no);
            }
        }

        public int q(int t) {
            return map.getOrDefault(binary_search(t), null);
        }

        // 二分查找查上限
        private int binary_search(int t) {
            int l = 0;
            int r = times.length - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (times[mid] <= t) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            return times[l] <= t ? times[l] : -1;
        }
    }


    /**
     * Your TopVotedCandidate object will be instantiated and called as such:
     * TopVotedCandidate obj = new TopVotedCandidate(persons, times);
     * int param_1 = obj.q(t);
     */
}
